package structure.array;


import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 地址：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
 * <p>
 * 题目：剑指 Offer 40. 最小的k个数
 * <p>
 * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 * <p>
 * 示例 1：
 * <p>
 * 输入：arr = [3,2,1], k = 2
 * 输出：[1,2] 或者 [2,1]
 * 示例 2：
 * <p>
 * 输入：arr = [0,1,2,1], k = 1
 * 输出：[0]
 */
public class Leetcode_Sword_Offer_40 {
    public static void main(String[] args) {

        int[] input = new int[]{3, 2, 1};
        int[] input1 = new int[]{0, 1, 2, 1};

        int[] leastNumbers = getLeastNumbers(input, 2);
        for (int leastNumber : leastNumbers) {
            System.out.println(leastNumber);
        }

        int[] leastNumbers1 = getLeastNumbers(input1, 2);
        for (int leastNumber : leastNumbers1) {
            System.out.println(leastNumber);
        }
        System.out.println(getLeastNumbers(input, 2).toString());
        System.out.println(getLeastNumbers(input1, 1).toString());


    }

    /**
     * 解法2：
     * 思路： 根据值去找下标。
     * <p>
     * 时间复杂度：O(N)
     * 空间复杂度：O(1)
     * <p>
     * 考虑边界条件：
     * 1、数组为空
     * <p>
     * <p>
     * 执行结果：通过
     * 执行用时：1 ms, 在所有 Java 提交中击败了 83.76% 的用户
     * 内存消耗：46.3 MB, 在所有 Java 提交中击败了 51.08% 的用户
     * <p>
     * <p>
     *
     * @return
     */
    public static int[] getLeastNumbers(int[] arr, int k) {
        int[] res = new int[k];
        if(k == 0){
            return res;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < arr.length; i++) {
            if (queue.size() < k) {
                queue.add(arr[i]);
            } else if (queue.peek() > arr[i]) {
                queue.poll();
                queue.add(arr[i]);
            }
        }
        for (int i = k - 1; i >= 0; i--) {
            res[i] = queue.poll();
        }
        return res;
    }


    /**
     * 解法1：
     * 思路： 排序，快速排序
     * <p>
     * 时间复杂度：O(NlogN)
     * 空间复杂度：O(logN) 排序的空间复杂度是 O(logN)
     * <p>
     * 执行结果：通过
     * 执行用时：8 ms, 在所有 Java 提交中击败了63.54%的用户
     * 内存消耗：39.4 MB, 在所有 Java 提交中击败了87.98%的用户
     * <p>
     * 可以优化的地方在哪里？
     * 利用堆排序
     *
     * @return
     */
    public static int[] getLeastNumbers1(int[] arr, int k) {
        int[] res = new int[k];
        Arrays.sort(arr);
        for (int i = 0; i < res.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }
}
